#include <bits/stdc++.h>

using namespace std;

class NumArray {
    vector<int> tree;
    vector<int> mNums;
    int n ;
    public:
        NumArray(vector<int>& nums) {
            n = nums.size();
            tree.resize(n + 1, 0);
            for(int i = 1; i <= n; ++i){
                int num = nums[i-1];
                tree[i] += num;
                int nxt = i + (i & (-i));
                if(nxt <= n){
                    tree[nxt] += tree[i];
                }
            }
            this->mNums = nums;
        }
        
        void update(int index, int val) {
            int del = val - this->mNums[index];
            this->mNums[index] = val;
            for(int i = index + 1; i <= n; i += (i & -i)){
                tree[i] += del;
            }
        }
        int prefixSum(int index){
            // return Sum(nums[:index]) not include nums[index]
            int s = 0;
            while(index > 0){
                s += tree[index];
                index &= index - 1;
                // same as 
                // index -= (index & - index);
            }
            return s;
        }
        int sumRange(int left, int right) {
            return prefixSum(right + 1) - prefixSum(left);
        }
    };